// 等差数列划分二
class Solution {
    public:
        int numberOfArithmeticSlices(vector<int>& nums) {
            int n = nums.size();
            if(n < 3) return 0;
            unordered_map<long long,vector<int>> hash;
            for(int i = 0; i < n; i++)
            {
                hash[nums[i]].push_back(i);
            }
            int ret = 0;
            // 以j为结尾的最多个数
            vector<vector<int>> dp(n,vector<int>(n));
            for(int j = 2; j < n; j++)
            {
                for(int i = 1; i < j; i++)
                {
                    long long a = (long long)2*nums[i] - nums[j];
                    if(hash.count(a) > 0)
                    {
                        for(auto &k : hash[a])
                        {
                            if( k < i) dp[i][j] += dp[k][i] + 1;
                        }
                    }
                    ret += dp[i][j];
                }
            }
    
            return ret;
        }
    };